1. Field of the Invention
The present invention relates to an arithmetic unit suitable for a correlation operation, a correlation arithmetic unit using such an arithmetic unit and a dynamic image compression apparatus using such a correlation arithmetic unit.
2. Description of the Related Art
It is necessary for a control of a mobile robot and an automatic traveling of a motorcar to measure a velocity vector in a camera screen. A control for the movement and the traveling is performed on the basis of the measured vector.
The velocity vector will be described referring to FIG. 1. Now, in the consideration of a circular figure in the space, as the robot moves, the circular figure moves in the position between the previous screen obtained through a camera and the present screen. This movement and its direction (or a movement vector) is measured. The measured movement vector divided by a time interval between the previous screen and the present screen gives the velocity vector.
In order to measure the movement vector, a two-dimensional correlation is used. A small area (a rectangle defined by a dotted line) of the previous screen is shifted on a two-dimensional basis by an arbitrary vector(.DELTA..sub.x, .DELTA..sub.y) to take a correlation with a small area (a rectangle defined by a solid line) of the present screen. When the shift vector (.DELTA..sub.x, .DELTA..sub.y), wherein the correlation becomes the maximum, is detected, it is the movement vector to be determined.
In the field of communications, a "movement compensation" is performed for a compression of a dynamic image. It will be explained referring to FIG. 1. The circle in the present screen is equivalent to a translation of the circle in the previous screen. Thus, there is no need to transmit image data as to the circle as image data of the present screen. It is sufficient to transmit only a movement vector so that the circle data on the previous screen is shifted to be displayed. Thus, a remarkable image compression is carried out. This scheme is used in International Standardization such as an MPEG. The two-dimensional correlation is used also for a measurement of the movement vector.
Also, in a pattern matching used in a pattern recognition and the like, it is necessary to detect a pattern matched in two screens and determine a vector as to their interval. The two-dimensional correlation is used also for such a matching.
The two-dimensional correlation is calculated, assuming that a luminance of a pixel (x, y) in a small area of the present screen is represented by a(x, y) and a luminance of a pixel shifted by (.DELTA..sub.x, .DELTA..sub.y) in a small area of the previous screen is represented by b (x+.DELTA..sub.x, y+.DELTA..sub.y), in the form of the product and sum of their whole pixels in accordance with the following equation. EQU C (.DELTA..sub.x, .DELTA..sub.y)=.SIGMA..sub.x .SIGMA..sub.y a (x, y) b (x+.DELTA..sub.x, y+.DELTA..sub.y) (5)
Where the accumulation of x and y is performed throughout small areas.
However, since the "product" of the above equation needs a large scale of hardware as compared with addition and subtraction, the product is replaced by the "absolute value of the difference", the two-dimensional correlation is calculated in accordance with the following equation. EQU C (.DELTA..sub.x, .DELTA..sub.y)=.SIGMA..sub.x .SIGMA..sub.y .vertline.a (x, y)-b (x+.DELTA..sub.x, y+.DELTA..sub.y).vertline. (6)
This replacement involves several drawbacks. The correlation expressed by equation (5) takes the maximum value when both the small areas match with one another (or when a travel equivalent to the movement vector is implemented), and takes the smaller value when both the small areas do not match with one another. Thus, it is possible to detect the maximum value so as to detect the movement vector with great accuracy. On the other hand, the correlation expressed by equation (6) takes the value zero when both the small areas match with one another, and takes the larger value when both the small areas do not match with one another. Consequently, the minimum value is detected to detect the movement vector. However, the correlation expressed by equation (6) takes the smaller value not only when both the small areas match with one another, but also when luminance of the screen is small in its entirety. Thus, there remains the problem in a reliability of the minimum value detection. Further, the noise mixed into the screen causes the correlation to vary, and thus a detection of the minimum value is insecure. According to equation (5), the correlation value becomes zero when luminance of one of the screens is zero. This indicates that it is involved in a non-correlation. On the contrary, according to equation (6), luminance of another of the screens becomes a correlation value. Thus, there remains the problem in a determination of the correlation.